package baseclass.j_dp.dp.fullBag;

import java.util.Arrays;

/**
 * 给定不同面额的硬币 coins 和一个总金额 amount。
 * 编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
 * 如果没有任何一种硬币组合能组成总金额，返回 -1。
 * <p>
 * 示例 1:
 * <p>
 * 输入: coins = [1, 2, 5], amount = 11
 * 输出: 3
 * 解释: 11 = 5 + 5 + 1
 * 示例 2:
 * <p>
 * 输入: coins = [2], amount = 3
 * 输出: -1
 * 说明:
 * 你可以认为每种硬币的数量是无限的。
 * <p>
 * 正常的思维是尽量先换大的，然后换次大的。使用贪心策略。然后贪心策略是错误的，举例
 * {1,4,9,10},amount = 13。 使用贪心先换10，然后剩余3，从比3小的换，3个1。要4个组合。
 * 事实上只需要9+4
 * <p>
 * 此题的本质是枚举，同完全平方数一样。
 * <p>
 * 设n为当前余额，f(n)为最优解，那么f(n) = f(n - coin) + 1, coin遍历整个coins。
 * <p>
 * 注意使用暴力递归会有重复子问题，如f(8) = f(5) + f(3)  ,f(5)依赖f(2),f(3)也依赖f(2)。
 * 可以使用带记忆回溯，最后转DP。典型的DP问题。
 *
 * @date 2020/3/3 20:05
 */
public class Code02_ChangeMoneyLessCount {
    public static int process1(int[] coins, int index, int amount) {
        //返回值是需要的硬币张数，不是总兑换种数，所以不返回1
        if (amount == 0) return 0;
        //assert amount > 0
        if (index >= coins.length) return -1;
        int res = Integer.MAX_VALUE;
        for (int count = 0; coins[index] * count <= amount; count++) {
            //余额为amount - count * coins[index]时，子问题兑换需要的硬币数
            int subCount = process1(coins,
                    index + 1, amount - count * coins[index]);
            if (subCount == -1) continue;
            //该问题的解 =  子问题的硬币数 + 当前花费的硬币数
            res = Math.min(res, count + subCount);
        }
        //if res = MAX, all the temp = -1
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    /**
     * 暴力回溯的重复子问题：[1,2,3,....],
     * 换2个1和0个2   和  换0个1以及1个2  来到3时子问题重复
     * <p>
     * memo[i][j]表示前i种硬币能够凑成总金额 j所需要最少的纸币数
     */
    public static int process2(int[] coins, int amount) {
        if (coins == null || coins.length == 0) return amount == 0 ? 0 : -1;

        //default all 0
        int[][] memo = new int[coins.length][amount + 1];
        return doProcess2(coins, 0, amount, memo);
    }

    private static int doProcess2(int[] coins, int index, int amount, int[][] memo) {
        if (amount == 0) return 0;
        //assert amount > 0
        if (index >= coins.length) return -1;
        if (memo[index][amount] != 0) return memo[index][amount];
        int res = Integer.MAX_VALUE;
        for (int count = 0; coins[index] * count <= amount; count++) {
            //余额为amount - count * coins[index]时，子问题兑换需要的硬币数
            int temp = doProcess2(coins, index + 1, amount - count * coins[index], memo);
            if (temp == -1) continue;
            //该问题的解 =  子问题的硬币数 + 当前花费的硬币数
            res = Math.min(res, count + temp);
        }
        //if res = MAX, all the temp = -1
        return memo[index][amount] = (
                res == Integer.MAX_VALUE ? -1 : res);
    }
    /**
     * 完全背包:
     * 方程：dp[i][j] = Math.min(dp[i-1][j],dp[i-1][j-k*coins[i]] + k)  k从1取
     */
    public static int dp(int[] coins, int amount) {
        if (coins == null || coins.length == 0) return amount == 0 ? 0 : -1;
        int[][] dp = new int[coins.length][amount + 1];
        for (int[] ints : dp) {
            Arrays.fill(ints, Integer.MAX_VALUE);
        }
        //用coins[0]来说，amount%coins[0] == 0下才能换，其他的都换不了
        //dp[0][0]代表用0号硬币兑换面值为0的钱，显然不可能，注意填充0，而不是Inter.MAX
        //这里比较特殊，因为dp[0][j-coins[i]]当 j = coins[i]时显然能换,
        //返回值是dp[0][j-coins[i]] + 1 = 1 ，代表用1张可以换。

        for (int j = 0; j <= amount; j++) {
            if (j % coins[0] == 0) dp[0][j] = j / coins[0];
        }
        for (int i = 1; i < coins.length; i++) {
            for (int j = 0; j <= amount; j++) {
                //j为当前账户总额,如果coins[i]不要，则dp[i][j] = dp[i-1][j]
                dp[i][j] = dp[i-1][j];
                for (int k = 1; k * coins[i] <= j; k++) {
                    //如果当前账户 j - k * coins[i] 能被使用，则在原来基础上➕ K枚硬币
                    if (dp[i - 1][j - k * coins[i]] != Integer.MAX_VALUE) {
                        dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - k * coins[i]] + k);
                    }
                }

            }
        }
        return dp[coins.length - 1][amount] == Integer.MAX_VALUE
                ? -1 : dp[coins.length - 1][amount];
    }

    /**
     * 完全背包问题转01背包：
     * 方程：dp[i][j] = Math.min(dp[i-1][j],dp[i][j-coins[i]] + 1)
     * <p>
     * 01背包方程：
     * dp[i][j] = Math.min(dp[i-1][j],dp[i-1][j-coins[i]] + 1)
     */
    public static int dp1(int[] coins, int amount) {
        if (coins == null || coins.length == 0) return amount == 0 ? 0 : -1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        //用coins[0]来说，amount%coins[0] == 0下才能换，其他的都换不了
        //dp[0]代表用0号硬币兑换面值为0的钱，显然不可能，注意填充0，而不是Inter.MAX
        //这里比较特殊，因为dp[j-coins[i]]当 j = coins[i]时显然能换,
        //返回值是dp[j-coins[i]] + 1 = 1 ，代表用1张可以换。
        for (int i = 0; i <= amount; i++) {
            if (i % coins[0] == 0) dp[i] = i / coins[0];
        }
        for (int i = 1; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                // == MAX 代表子问题不能换
                if (dp[j - coins[i]] != Integer.MAX_VALUE) {
                    //dp[j-coins[i]]当 j = coins[i]时显然能换，所以需要1张即可。
                    //从而初始值dp[0] = 0 有着额外的意义。
                    dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }



    public static void main(String[] args) {
        int amount = 4;
        int[] coins = {1, 2};
        System.out.println(process1(coins, 0, amount));
        System.out.println(process2(coins, amount));
        System.out.println(dp(coins, amount));
        System.out.println(dp1(coins, amount));
        for (int i = 0; i < 10000000; i++) {
            coins = generateRandomArray(3, 5);
            amount = (int) (Math.random() * 5);
            try {
                if (dp1(coins, amount) != dp(coins, amount)) {
                    System.out.println(Arrays.toString(coins));
                    System.out.println("amount = " + amount);
//                    break;
                }
            } catch (Exception e) {
                System.out.println(Arrays.toString(coins));
            }
        }
    }

    // for test
    private static int[] generateRandomArray(int maxSize, int maxValue) {
        //产生 [0-maxsize]随机长度的数组
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            //随机产生数据
            int value = (int) ((maxValue + 1) * Math.random());
            if (value == 0) value++;
            arr[i] = value;
        }
        return arr;
    }

}
